package interview.sort;//Java 代码实现

import com.study.interfaces.IArraySort;
import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.util.LogUtil.info;

/**
 * 3. 插入排序
 * <p>
 * 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
 * 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元
 * 素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
 */
@Slf4j
@SuppressWarnings("all")
public class InsertSort implements IArraySort {

    @Override
    public int[] sort(int[] arr) {
        // 190504 first
        // 190510 second
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {

            // 记录要插入的数据
            int tmp = arr[i];

            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }

            // 存在比其小的数，插入
            if (j != i) {
                arr[j] = tmp;
            }

        }
        return arr;
    }

    @Test
    public void test() {
        info(sort(new int[]{2, 1, 4, 3, 5}));
    }
}














































/*
public int[] sort(int[] arr) {
    // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
    for (int i = 1; i < arr.length; i++) {

        // 记录要插入的数据
        int tmp = arr[i];

        // 从已经排序的序列最右边的开始比较，找到比其小的数
        int j = i;
        while (j > 0 && tmp < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }

        // 存在比其小的数，插入
        if (j != i) {
            arr[j] = tmp;
        }

    }
    return arr;
}
*/
